#ifdef a 
#include"Heap.h"


//交换函数
void Swap(HTYPE* left, HTYPE* right) {
	HTYPE temp = *left;
	*left = *right;
	*right = temp;
	return;
}

//建立小堆
void AdjustDown(Heap* hp,HTYPE parent) {
	HTYPE child = parent * 2 + 1;
	//左孩子存在
	while (child < hp->size) {
		//右孩子存在且对左右孩子进行比较
		if (child + 1 < hp->size && hp->harray[child] > hp->harray[child + 1]) {
			//左孩子大于右孩子
			child += 1;
		}
		if (hp->harray[child] < hp->harray[parent]) {
			Swap(&hp->harray[child], &hp->harray[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			return;
		}
	}
	return;
}

//容量
int HeapManyCapacity(Heap* hp) {
	assert(hp);
	return hp->capacity;
}

//堆的初始化
void HeapInit(Heap* hp, HTYPE* array, int size) {
	assert(hp);
	hp->harray = (HTYPE*)malloc(sizeof(HTYPE) * size);
	if (!hp->harray) {
		assert(hp->harray);
		return;
	}
	memcpy(hp->harray, array, sizeof(HTYPE) * size);
	hp->capacity = size;
	hp->size = size;
	for (int i = (size - 2) / 2; i >= 0; i--)
		AdjustDown(hp, i);
	return;
}


//判断堆是否为空
int HeapEmpty(Heap* hp) {
	assert(hp);
	return hp->size == 0;
}

//扩容
void CheckCapacity(Heap* hp) {
	assert(hp);
	if (hp->capacity == hp->size) {
		HTYPE* temp = (HTYPE*)realloc(hp->harray, sizeof(HTYPE) * 2 * hp->capacity);
		if (!temp) {
			assert(temp);
			return;
		}
		hp->harray = temp;
		hp->capacity *= 2;
	}
	return;
}

//向上调整
void AdjustUp(Heap* hp, HTYPE child) {
	assert(hp);
	int parent = (child - 1) / 2;
	while (child) {
		if (hp->harray[parent] > hp->harray[child]) {
			Swap(&hp->harray[parent], &hp->harray[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			return;
		}
	}
	return;
}

//堆的插入
void HeapPush(Heap* hp, HTYPE data) {
	CheckCapacity(hp);
	hp->harray[hp->size++] = data;
	AdjustUp(hp, hp->size - 1);
	return;
}

//获取堆顶元素
HTYPE HeapTop(Heap* hp) {
	assert(hp);
	if (HeapEmpty(hp))
		assert(0);
	return hp->harray[0];
}

//堆的有效元素个数
int HeapSize(Heap* hp) {
	assert(hp);
	return hp->size;
}

//堆的销毁
void HeapDestory(Heap* hp) {
	assert(hp);
	if (hp->harray) {
		free(hp->harray);
		hp->harray = NULL;
		hp->capacity = 0;
		hp->size = 0;
	}
	return;
}

//堆的删除
void HeapErase(Heap* hp) {
	if (HeapEmpty(hp))
		return;
	Swap(&hp->harray[0], &hp->harray[hp->size - 1]);
	hp->size--;
	AdjustDown(hp, 0);
	return;
}


//--------------------------------------------------------------------------------------------------
//测试
void TestHeap() {
	Heap hp;
	HTYPE array[] = { 27,15,19,18,28,34,65,49,25,37 };
	HeapInit(&hp, array, sizeof(array) / sizeof(array[0]));
	printf("top = %d\n ", HeapTop(&hp));
	printf("size = %d\n", HeapSize(&hp));
	printf("capacity = %d\n", HeapManyCapacity(&hp));
	printf("\n\n");

	HeapPush(&hp, 1);//插入
	HeapPush(&hp, 2);//插入
	printf("top = %d\n ", HeapTop(&hp));
	printf("size = %d\n", HeapSize(&hp));
	printf("capacity = %d\n", HeapManyCapacity(&hp));
	printf("\n\n");

	HeapPush(&hp, 3);//插入
	printf("top = %d\n ", HeapTop(&hp));
	printf("size = %d\n", HeapSize(&hp));
	printf("capacity = %d\n", HeapManyCapacity(&hp));
	printf("\n\n");

	//删除
	HeapErase(&hp);
	printf("top = %d\n ", HeapTop(&hp));
	printf("size = %d\n", HeapSize(&hp));
	printf("capacity = %d\n", HeapManyCapacity(&hp));
	printf("\n\n"); 
	
	HeapDestory(&hp);
	printf("capacity = %d\n", HeapManyCapacity(&hp));
	return;
}

#endif